Năm 1902, chính quyền thực dân Pháp đã cho thành lập trường Paul Bert (Collège Paul Bert)tại Hà Nội để đào tạo bậc trung học bán phần cho con các quan chức Pháp tại Đông Dương, đồng thời các con quan chức cao cấp người Việt làm cho Pháp, nhằm đào tạo đội ngũ kế tiếp làm việc cho Pháp tại Đông Dương. Trường sở được đặt tại Boulevard Rollandes[1] Nay là Trường Trung học Phổ thông Trần Phú - Hoàn Kiếm.

Năm 1913, Toàn quyền Đông Dương Albert Sarraut đã ra quyết định nâng bậc trường Paul Bert từ Collège lên bậc Lycée để thành lập một trường trung học toàn phần như các trường ở chính quốc với đầy đủ cơ sở vật chất phục vụ cho việc dạy và học tại Hà Nội. Trường có nhiệm vụ thu nhận học sinh người Pháp và cả học sinh là con em các quan chức cao cấp người Việt Nam, người Miên, người Lào.[2]

Năm 1914, công trình xây dựng trường sở mới được khởi công trên một khuôn viên rộng, vuông vắn, nằm trước Phủ Toàn quyền, giới hạn bởi bốn con đường Avenue de la République (Đại lộ Cộng hòa)[3], Avenue Brière de l'isle[4], Boulevard Carnot[5] và Rue Destenay[6].

Công trình do Kiến trúc sư Adolphe Bussy thiết kế, gồm khu trường chính với khu học đường, khu nội trú, khu y tế; và khu giáo dục thể chất gồm 1 sân bóng đá, 1 sân bóng rổ, 1 sân bóng chuyền, 1 khu điền kinh (hố cát để tập nhảy cao, nhảy xa, xà đơn, xà kép, xà lệch…) để phục vụ nhu cầu cao của các học sinh tầng lớp trên. Hai khu này được ngăn cách bởi phố Destenay. Vị trí khu trường chính tương ứng với trụ sở Trung ương Đảng Cộng sản Việt Nam ngày nay. Vị trí khu giáo dục thể chất về sau được dùng để xây trụ sở Ban Tư tưởng Văn hóa Trung ương.

Công trình được hoàn tất đầu năm 1919. Sau khi hoàn thành trường sở, trường Lycée Paul Bert được đổi tên thành Trường Trung học Hà Nội (Lycée de Hanoi). Một phân sở của Lycée de Hanoi chuyên đào tạo các lớp trên được chuyển về đây. Riêng phân sở chuyên đào tạo các lớp dưới vẫn ở lại trường sở cũ. Thời bấy giờ, để phân biệt, người ta thường gọi phân sở tại Boulevard Rollandes là Petit Lycée (trường Trung học Nhỏ); còn phân sở tại Avenue de la République là Grand Lycée (trường Trung học Lớn).[7]

Năm 1923, trường được xây thêm mặt tiền chính (façade principale) ở hướng Avenue de la République. Theo Nghị định ngày 24 tháng 7 năm 1923 của Toàn quyền Đông Dương tạm thời François Baudoin, trường đổi tên thành Trường Trung học Alber Sarraut (Lycée Albert Sarraut) để kỷ niệm cựu Toàn quyền Đông Dương Albert Sarraut, người ra quyết định lập trường, bấy giờ đang giữ chức Bộ trưởng Bộ Thuộc địa Pháp[2]. Phân sở Petit Lycée lấy lại tên cũ là Lycée Paul Bert.